using System.Text;

namespace DataStructure
{
    class SortedArray2<Key,Value> where Key : IComparable<Key>
    {
        private Key[] keys;
        private Value[] values;
        private int N;

        public SortedArray2(int capacity)
        {
            keys = new Key[capacity];
            values = new Value[capacity];
        }

        public SortedArray2() : this(10) { }

        public int Count { get { return N; } }

        public bool IsEmpty => N == 0;


        public int Rank(Key key)
        {
            //在[l-r]中寻找key
            int l = 0;
            int r = N-1;

            while (l <= r)
            {
                int mid = l + (r - l) / 2;

                if (key.CompareTo(keys[mid]) < 0)
                    r = mid - 1;

                else if (key.CompareTo(keys[mid]) > 0)
                    l = mid + 1;

                else
                    return mid;//找到key并返回索引下标
            }
            return l;
        }

        public Value Get(Key key)
        {
            if (IsEmpty)
                throw new ArgumentException("数组为空");

            int i =Rank(key);

            if (i<N && keys[i].CompareTo(key) == 0)
                return values[i];
            else
                throw new ArgumentException("键"+key+ "不存在");
        }
        public void Add(Key key,Value value)
        {
            int i = Rank(key);

            if (N == keys.Length)
                ResetCapacity(2 * keys.Length);

            if (i < N && keys[i].CompareTo(key) == 0)
            {
                values[i] = value;
                return;
            }

            for (int j = N - 1; j >= i; j--)
            {
                keys[j + 1] = keys[j];
                values[j + 1] = values[j];
            }

            keys[i] = key;
            values[i] = value;
            N++;
        }

        public void Remove(Key key)
        {
            if (IsEmpty)
            {
                return;
            }
            int i = Rank(key);

            if (i == N || keys[i].CompareTo(key) != 0)
                return;

            for (int j = i + 1; j <= N - 1; j++)
            {
                keys[j - 1] = keys[j];
                values[j-1] = values[j];
            }

            N--;
            keys[N] = default(Key);
            values[N] = default(Value);

            if (N == keys.Length / 4)
                ResetCapacity(keys.Length / 2);

        }
        //获取最小键
        public Key Min()
        {
            if (IsEmpty)
                throw new ArgumentException("数组为空");

            return keys[0];
        }
        //获取最大键
        public Key Max()
        {
            if (IsEmpty)
                throw new ArgumentException("数组为空");

            return keys[N-1];
        }
        //选出排名为k的键
        public Key Select(int k)
        {
            if (k == 0 || k >= N)
                throw new ArgumentException("索引越界");

            return keys[k];
        }

        //查找是否在数组中
        public bool Contains(Key key)
        {
            int i = Rank(key);

            if (i < N && keys[i].CompareTo(key) == 0)
                return true;

            return false;
        }
        //找出小于或等于key的最大键
        public Key Floor(Key key)
        {
            int i = Rank(key);

            if (i < N && keys[i].CompareTo(key) == 0)
                return keys[i];

            if (i == 0)
                throw new ArgumentException("没有找到小于和等于" + key + "的最大值");

            else
                return keys[i - 1];
        }
        //找出大于或等于key的最大键
        public Key Ceiling(Key key)
        {
            int i = Rank(key);

            if (i == N)
                throw new ArgumentException("没有找到大于和等于" + key + "的最大值");
            else
                return keys[i];
        }

        //调整数组容量的大小
        private void ResetCapacity(int newCapacity)
        {
            Key[] newKeys = new Key[newCapacity];
            Value[] newValues = new Value[newCapacity];

            for (int i = 0; i < N; i++)
            {
                newKeys[i] = keys[i];
                newValues[i] = values[i];
            }

            keys = newKeys;
            values = newValues;
        }
        //输出有序数组的信息
        public override string ToString()
        {
            StringBuilder res = new StringBuilder();

            res.Append("[");
            for (int i = 0; i < N; i++)
            {
                res.Append("{" + keys[i] + "," + values[i] + "}");
                    if (i != N - 1)
                    res.Append(", ");
            }
            res.Append("]");
            return res.ToString();
        }
    }
}